#!/usr/bin/python
#-*-encoding:utf-8-*-

import pdb
import sys

# 一个二叉树的节点:
#      Node
#     /   \
#    /     \
#  left    right
class HanoNode:
    def __init__(self, begin, base, end, plates):
        self.begin  = begin
        self.end    = end
        self.base   = base

        self.plates = plates        # 汉诺节点上盘子数目
        self.visit  = 2             # 汉诺节点的子节点数目

    def getLeft(self):
        # 如果子节点数目为2(表示没有访问过该节点),
        # 并且该点依旧有要移动的盘子
        # 那么先访问节点的左子树: 返回左子树: 左子树以后不可再访问: 子节点数减一
        if (self.visit == 2) and (self.plates > 1):
            self.visit -= 1
            return HanoNode(self.begin, self.end, self.base, self.plates - 1)
        else:
            return None

    def getRight(self):
        # 如果子节点数目为1(表示已访问过左节点: 现在该访问右节点),
        # 并且该点依旧有要移动的盘子
        # 那么现在可以访问右子树了
        if(self.visit == 1) and (self.plates > 1):
            self.visit -= 1         # 子节点减1
            return HanoNode(self.base, self.begin, self.end, self.plates - 1)    # 返回右子树
        else:
            return None

def getEndStack( stack = [] ):
    if len(stack) > 0:
        return  stack[ len(stack) - 1 ]
    else:
        return None

if __name__ == "__main__":

    plates = int(sys.argv[1])          # 从命令行获取盘子数目
    root = HanoNode(1, 2, 3, plates)   # 定义一个Hano 对象: 代表汉诺达的根节点
    stack = []                         # 中序遍历Hano树, 将节点按中序遍历放入列表中( 模拟递归时函数栈的存储 )
    stack.append( root )               # 首先将HanoNode的根节点放入栈中
#pdb.set_trace()

    count = 0

    # while( len(stack) > 0 ):
    while( stack ):
        endEle = getEndStack(stack)

        # 总是将末尾节点的左节点压入stack[] 中: 直到最底层节点没有左节点为止
        leftEle = endEle.getLeft()
        if leftEle:
            stack.append(leftEle)
            continue

        #############################

        # 如果一个节点没有左节点: 那么说明树左边遍历到底了: 输出移动: 然后遍历节点的右节点
        # 并将最后一个节点出栈
        rightEle = endEle.getRight()
        count += 1
        print count,
        print ": ",
        print endEle.begin,
        print " -> ",
        print endEle.end,
        print
        stack.pop()

        if rightEle:
            stack.append(rightEle)
            continue


# vim: set fdm=indent  fdl=5:
